/**
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
 * 测试用例保证结果在 32 位有符号整数范围内。
 * 
 * 1 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 */


class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(),m = t.size();
        vector memo(n,vector<int>(m,-1));
        auto dfs = [&](this auto&& dfs,int i,int j)->int{
            if(i < j)return 0;
            if(j < 0)return 1;
            int& res = memo[i][j];
            if(res != -1){
                return res;
            }
            res = dfs(i - 1,j);
            if(s[i] == t[j]){
                res += dfs(i - 1,j - 1);
            }
            return res;
        };
        return dfs(n - 1,m - 1);
    }
};